package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-22 0:02
 */
public class Walk {
    public int walking(int N,int cur,int rest,int P){
        //编写递归出口
        if(rest==0){
            if(cur==P){
                return 1;
            }else {
                return 0;
            }
        }
        //排除特殊情况，在0位置处：只能往后走
        if(cur==1){
            return walking(N, cur+1, rest-1, P);
        }
        //在最后一个位置，只能往前走
        if(cur==N){
            return walking(N, cur-1, rest-1, P);
        }
        //在中间，可以往前往后走
        return walking(N, cur-1, rest-1, P)+walking(N, cur+1, rest-1, P);


        }
        public int walkCache(int N,int cur,int rest ,int [][]dp,int P){
        if(dp[cur][rest]!=-1){
            return dp[cur][rest];
        }
        if(rest==0){
            dp[cur][rest]=cur==P?1:0;
            return dp[cur][rest];
        }
        if(cur==1){
            dp[cur][rest]=walkCache(N, cur+1, rest-1, dp,P);
            return dp[cur][rest];
        }
        if(cur==N){
            dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P);
            return dp[cur][rest];
        }
            return dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P)+walkCache(N, cur+1, rest-1,dp, P);
        }
    }

